\section{Preliminary computational experiments}

In this section we provide preliminary computational experiments with the proposed method.
To this end, we implemented the cut generating procedure to compute
a strengthened upper bound for the maximum stable set problem. Whenever a
fractional solution is found, we execute the cut generating procedure several
times, each execution starting from a different clique in the role of $W_1$. 
% For each
% initial clique, we generate a sequence of clique projections with a greedy algorithm that tries to avoid repetition of vertices already belonging to a clique in the sequence. In order to ensure that the initial
% cliques are not repeated, we employ a backtracking-based algorithm introduced in
% \cite{Ostergard.01} that in principle enumerates all cliques in the graph. 
We project each clique in the sequence, until a simple greedy heuristic finds a violated clique inequality.
When this happens, we apply the clique lifting procedure of Lemma~\ref{lem:stlifting} and add the generated inequality if it is violated by the fractional solution at hand.
The experiments were performed on a 32-bit i5 computer with 2Gb of memory
having the cut generating procedure attached to the Cplex
12.6’s branch and cut algorithm.
% The preprocessing, cut generation, and variable fixing procedures from Cplex
 % were turned off.

Table~\ref{tab:resultsDIMACS} summarizes the preliminary experiments with some
instances from the DIMACS benchmark and for random graphs.
The notation $n\_d$ specifies random graphs with $n$ vertices and a density of
$d/100$, and for these instances we report the average results over five
randomly-generated instances. The first four
columns contain the instance name, the number of vertices, the graph density,
and its stability number. The following three columns contain the upper bounds with
our procedure (column ``Rank/W'' indicates rank/generalized rank inequalities),
with clique cuts only, and obtained in \cite{Pardalos}, respectively.
The column ``Time'' reports the total computation time in seconds.
Finally, we report the number of generated rank inequalities/generalized rank
inequalities (column ``Rank/W''), and clique cuts (column ``Clique'').

As Table~\ref{tab:resultsDIMACS} shows, and similarly to the results
in~\cite{Correa14}, the procedure is able to generate a large number of cuts,
and provides upper bounds that are competitive with those generated in previous
procedures. As a future work, we intend to perform extensive computational experiments
with the proposed cut generating procedure applied for other optimization problems
involving stable sets, like, for instance, the vertex coloring problem.

\begin{table*}[htbp]
\caption{Results for graphs selected from the DIMACS benchmark and
randomly generated.}
\label{tab:resultsDIMACS}
\centering
{\scriptsize
\begin{tabular}{ccrcccrrrr} \hline
%Encabezado fila 1
\multicolumn{3}{l}{Instances} & \multicolumn{3}{l}{UB per type of cuts} &
\multicolumn{1}{r}{Time (sec.)} & \multicolumn{2}{l}{Number of cuts} \\
\cline{1-3} \hline
%Encabezado fila 2
$G=(V,E)$ & $|V|$/Dens. & $\alpha(G)$ & Rank/W & Clique & \cite{Pardalos} &&
Rank/W & Clique \\ \hline
\hline
%Datos
\input{resultados2.0-dimacs.tex}
\hline \hline
\input{resultados2.0-rand.tex}
 \hline
\end{tabular}}
\end{table*}
